#define M 40010
int gap[M],dis[M],pre[M],cur[M];
int NE,NV;
int head[M];
struct Node{
	int c,pos,next;
}E[999999];
int sap(int s,int t) {
	memset(dis,0,sizeof(int)*(NV+1));
	memset(gap,0,sizeof(int)*(NV+1));
	FF(i,NV) cur[i] = head[i];
	int u = pre[s] = s,maxflow = 0,aug = -1;
	gap[0] = NV;
	while(dis[s] < NV) {
loop:		for(int &i = cur[u]; i != -1; i = E[i].next) {
			int v = E[i].pos;
			if(E[i].c && dis[u] == dis[v] + 1) {
				checkmin(aug,E[i].c);
				pre[v] = u;
				u = v;
				if(v == t) {
					maxflow += aug;
					for(u = pre[u];v != s;v = u,u = pre[u]) {
						E[cur[u]].c -= aug;
						E[cur[u]^1].c += aug;
					}
					aug = -1;
				}
				goto loop;
			}
		}
		int mindis = NV;
		for(int i = head[u]; i != -1 ; i = E[i].next) {
			int v = E[i].pos;
			if(E[i].c && mindis > dis[v]) {
				cur[u] = i;
				mindis = dis[v];
			}
		}
		if( (--gap[dis[u]]) == 0)	break;
		gap[ dis[u] = mindis+1 ] ++;
		u = pre[u];
	}
	return maxflow;
}
void Insert(int u,int v,int c,int cc = 0) {
	E[NE].c = c;	E[NE].pos = v;
	E[NE].next = head[u];	head[u] = NE++;
	E[NE].c = cc;	E[NE].pos = u;
	E[NE].next = head[v];	head[v] = NE++;
}
 
int main() {
	FF(i,NV) head[i] = -1;
	NE = 0;
}

